package neo.aoi;

import artofillusion.math.BoundingBox;
import artofillusion.math.Vec3;

/**
 * This class defines a triangle in 3D space. Some utility functions are
 * implemented such as intersection with other figures.
 * 
 * @author Carlos Martinez
 */
public class Triangle {
	/* The corners of the triangle */
	private Vec3 _a, _b, _c;

	private Plane _plane;

	private BoundingBox _bounds;

	/**
	 * Creates a new instance with the giving points indicating the vertices of
	 * the Triangle
	 * 
	 * @param a
	 *            Vertex of the triangle
	 * @param b
	 *            Vertex of the triangle
	 * @param c
	 *            Vertex of the triangle
	 */
	public Triangle(Vec3 a, Vec3 b, Vec3 c) {
		this._a = a;
		this._b = b;
		this._c = c;
		_plane = null; // Singleton
	}

	/**
	 * Returns the <code>Plane</code> where this triangle exists.
	 * 
	 * @return The plane which contains the triangle
	 */
	public Plane getPlane() {
		if (_plane == null)
			_plane = new Plane(_a, _b, _c);
		return _plane;
	}

	/**
	 * Checks for intersection between two triangles.
	 * 
	 * @param target
	 *            The other triangle to check intersection with.
	 * @return true if triangles intersect, false otherwise.
	 */
	public boolean intersects(Triangle target) {
		// Simple verification
		if (!getBoundingBox().intersects(target.getBoundingBox())) {
			return false;
		}

		Vec3 a1 = this._a;
		Vec3 b1 = this._b;
		Vec3 c1 = this._c;

		Vec3 a2 = target._a;
		Vec3 b2 = target._b;
		Vec3 c2 = target._c;

		// Planes where triangles live
		Plane p1 = getPlane();
		Plane p2 = target.getPlane();

		// Distances from Plane1 to Points of Triangle2
		double dp1_a2 = p1.distance(a2);
		double dp1_b2 = p1.distance(b2);
		double dp1_c2 = p1.distance(c2);

		// Distances from Plane2 to Points of Triangle1
		double dp2_a1 = p2.distance(a1);
		double dp2_b1 = p2.distance(b1);
		double dp2_c1 = p2.distance(c1);

		// Check for co-planar triangles
		if (dp1_a2 == 0 && dp1_b2 == 0 && dp1_c2 == 0) {
			// TODO: check for co-planar intersections...
			return false;
		}

		// Check for same sign... (+=true, -=false)
		boolean sign_a1 = dp2_a1 > 0;
		boolean sign_b1 = dp2_b1 > 0;
		boolean sign_c1 = dp2_c1 > 0;

		boolean sign_a2 = dp1_a2 > 0;
		boolean sign_b2 = dp1_b2 > 0;
		boolean sign_c2 = dp1_c2 > 0;

		if (sign_a1 == sign_b1 && sign_a1 == sign_c1 || sign_a2 == sign_b2
				&& sign_a2 == sign_c2) {
			// Triangle is on one side of plane. Intersection does not occur.
			return false;
		}

		// Select v1_0 and v1_2 on the same side of plane, and v1_1 on the other
		// side.
		Vec3 v1_0, v1_1, v1_2;
		double dv1_0, dv1_1, dv1_2;
		if (sign_a1 != sign_b1 && sign_b1 == sign_c1) {
			v1_1 = a1; // Odd one
			dv1_1 = dp2_a1;
			v1_0 = b1;
			v1_2 = c1; // Same side
			dv1_0 = dp2_b1;
			dv1_2 = dp2_c1;
		} else if (sign_b1 != sign_a1 && sign_a1 == sign_c1) {
			v1_1 = b1; // Odd one
			dv1_1 = dp2_b1;
			v1_0 = a1;
			v1_2 = c1; // Same side
			dv1_0 = dp2_a1;
			dv1_2 = dp2_c1;
		} else if (sign_c1 != sign_a1 && sign_a1 == sign_b1) {
			v1_1 = c1; // Odd one
			dv1_1 = dp2_c1;
			v1_0 = a1;
			v1_2 = b1; // Same side
			dv1_0 = dp2_a1;
			dv1_2 = dp2_b1;
		} else {
			throw new ArithmeticException("Signs undefined!");
		}

		// Select v2_0 and v2_2 on the same side of plane, and v2_1 on the other
		// side.
		Vec3 v2_0, v2_1, v2_2;
		double dv2_0, dv2_1, dv2_2;
		if (sign_a2 != sign_b2 && sign_b2 == sign_c2) {
			v2_1 = a2; // Odd one
			dv2_1 = dp1_a2;
			v2_0 = b2;
			v2_2 = c2; // Same side
			dv2_0 = dp1_b2;
			dv2_2 = dp1_c2;
		} else if (sign_b2 != sign_a2 && sign_a2 == sign_c2) {
			v2_1 = b2; // Odd one
			dv2_1 = dp1_b2;
			v2_0 = a2;
			v2_2 = c2; // Same side
			dv2_0 = dp1_a2;
			dv2_2 = dp1_c2;
		} else if (sign_c2 != sign_a2 && sign_a2 == sign_b2) {
			v2_1 = c2; // Odd one
			dv2_1 = dp1_c2;
			v2_0 = a2;
			v2_2 = b2; // Same side
			dv2_0 = dp1_a2;
			dv2_2 = dp1_b2;
		} else {
			throw new ArithmeticException("Signs undefined!");
		}

		// Figure out line L where planes intersect
		// Cross product of the planes
		Vec3 d = p1.cross(p2);

		// Line of intersection
		// L = O + t * D
		Vec3 o = p2.intersects(v1_0, v1_1); // Some point on L

		/* Project points onto line - plane 1 */
		/* pv1_i = D . (V1_i - o) */
		double pv1_0 = d.dot(v1_0.minus(o));
		double pv1_1 = d.dot(v1_1.minus(o));
		double pv1_2 = d.dot(v1_2.minus(o));

		/* Project points onto line - plane 2 */
		/* pv1_i = D . (V1_i - o) */
		double pv2_0 = d.dot(v2_0.minus(o));
		double pv2_1 = d.dot(v2_1.minus(o));
		double pv2_2 = d.dot(v2_2.minus(o));

		/* Intervals of T */
		double t1_01 = pv1_0 + (pv1_1 - pv1_0) * dv1_0 / (dv1_0 - dv1_1);
		double t1_12 = pv1_1 + (pv1_2 - pv1_1) * dv1_1 / (dv1_1 - dv1_2);
		double t2_01 = pv2_0 + (pv2_1 - pv2_0) * dv2_0 / (dv2_0 - dv2_1);
		double t2_12 = pv2_1 + (pv2_2 - pv2_1) * dv2_1 / (dv2_1 - dv2_2);

		double min_1 = Math.min(t1_01, t1_12);
		double max_1 = Math.max(t1_01, t1_12);
		double min_2 = Math.min(t2_01, t2_12);
		double max_2 = Math.max(t2_01, t2_12);

		return !(max_1 < min_2) && !(max_2 < min_1);
	}

	/**
	 * Returns the minimum <code>BoundingBox</code> which contains this
	 * <code>Triangle</code> and is aligned with the coordinate axis
	 * 
	 * @return The <code>BoundingBox</code> arround this <code>Triangle</code>.
	 */
	public BoundingBox getBoundingBox() {
		if (_bounds == null) {
			double x1 = Math.min(Math.min(_a.x, _b.x), _c.x);
			double x2 = Math.max(Math.max(_a.x, _b.x), _c.x);
			double y1 = Math.min(Math.min(_a.y, _b.y), _c.y);
			double y2 = Math.max(Math.max(_a.y, _b.y), _c.y);
			double z1 = Math.min(Math.min(_a.z, _b.z), _c.z);
			double z2 = Math.max(Math.max(_a.z, _b.z), _c.z);
			_bounds = new BoundingBox(x1, x2, y1, y2, z1, z2);
		}
		return _bounds;
	}

	/**
	 * Test if 3D point is inside 3D Triangle.
	 * 
	 * @param p
	 *            the 3D point to check
	 * @return true if the point is inside the triangle, false otherwise
	 */
	public boolean intersect(Vec3 p) {
		long sign12, sign23, sign31;
		Vec3 vect12, vect23, vect31, vect1h, vect2h, vect3h;
		Vec3 cross12_1p, cross23_2p, cross31_3p;

		/* First, a quick bounding-box test: */
		/* If P is outside triangle bbox, there cannot be an intersection. */

		BoundingBox bbox = getBoundingBox();
		if (!bbox.contains(p)) {
			return false;
		}

		/*
		 * For each triangle side, make a vector out of it by subtracting
		 * vertexes;
		 */
		/* make another vector from one vertex to point P. */
		/* The crossproduct of these two vectors is orthogonal to both and the */
		/* signs of its X,Y,Z components indicate whether P was to the inside or */
		/* to the outside of this triangle side. */

		vect12 = _a.minus(_b);
		vect1h = _a.minus(p);
		cross12_1p = vect12.cross(vect1h);

		vect23 = _b.minus(_c);
		vect2h = _b.minus(p);
		cross23_2p = vect23.cross(vect2h);

		vect31 = _c.minus(_a);
		vect3h = _c.minus(p);
		cross31_3p = vect31.cross(vect3h);

		/* Extract X,Y,Z signs 0...63 integer */
		sign12 = sign3(cross12_1p);
		sign23 = sign3(cross23_2p);
		sign31 = sign3(cross31_3p);

		/* If all three crossproduct vectors agree in their component signs, */
		/* then the point must be inside all three. */
		/* P cannot be OUTSIDE all three sides simultaneously. */
		return (sign12 & sign23 & sign31) != 0;
	}

	/**
	 * Express the sign as a 8 bit number.
	 */
	private long sign3(Vec3 a) {
		return (a.x < 0 ? 4 : 0) | (a.x > -0 ? 32 : 0) | (a.y < 0 ? 2 : 0)
				| (a.y > -0 ? 16 : 0) | (a.z < 0 ? 1 : 0) | (a.z > -0 ? 8 : 0);
	}

	/**
	 * Returns the requested vertex identified by vertex number. First vertex
	 * has index 0. An <code>ArrayIndexOutOfBoundsException</code> is thrown
	 * if the requested vertex index is greater than 2.
	 * 
	 * @param index
	 *            the index of the requested vertex.
	 * @return the requested vertex.
	 */
	public Vec3 getVertex(int index) {
		switch (index) {
		case 0:
			return _a;
		case 1:
			return _b;
		case 2:
			return _c;
		default:
			throw new ArrayIndexOutOfBoundsException("No such vertex: " + index);
		}
	}
}
